<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <title>AStar寻路算法</title>
    <link rel="stylesheet" href="astar.css">
    <!--<link rel="stylesheet" href="astart-min.css">-->

    <style>
        * {
            margin: 0;
            padding: 0;
        }

        #contain {
            position: absolute;
            left: 50%;
            top: 50%;
            transform: translate(-50%, -50%);
        }

        .mod {
            position: absolute;
            left: 20%;
            top: 10%;
            transform: translate(-20%, -50%);
        }

        /*.cell, #youbiao {*/
        /*width: 60px;*/
        /*height: 60px;*/
        /*box-sizing: border-box;*/
        /*border: 1px solid lightgray;*/

        /*}*/

        /*#youbiao {*/
        /*background: green;*/
        /*position: absolute;*/
        /*left: 0;*/
        /*top: 0;*/
        /*}*/

        /*.row {*/
        /*display: flex;*/
        /*justify-content: space-between;*/
        /*flex-flow: nowrap;*/
        /*width: 600px;*/
        /*height: 60px;*/
        /*box-sizing: border-box;*/
        /*}*/

        .wall {
            background: black;
        }

        .endP {
            background: red;
        }

        span {
            color: #b88c4f;
            font-size: 15px;
            display: block;
        }

        .recent {
            background: lightgray;
        }

        .route {
            background-color: cornflowerblue;
        }
    </style>


</head>
<body>
<div class="mod">
    <span>A*寻路算法(二叉堆)</span>
    <span>地图类型</span>
    <select>
        <option value="0">随机地图</option>
        <option value="1">撞墙测试</option>
        <option value="2">死路测试</option>
        <option value="3">迷宫测试</option>
    </select>
    <span>地图大小</span>
    <select>
        <option value="0">10*10</option>
        <option value="1">20*20</option>
        <option value="2">30*30</option>
        <option value="2">60*60</option>
        <option value="2">100*100</option>
    </select>

</div>

</body>

<script src="jquery-3.2.1.js"></script>
<script src="map.js"></script>
<script>

       // var debug = true;
    var debug = false;

    //测试模式
    var test = 2;

    //个数
    var side = 60;


    //长度
    var len = 600 / side;

    var rowC = "row" + len;
    var cellC = "cell" + len;

    $("body").append("<div id='contain'></div>");
    for (var i = 0; i < side; i++) {

        $("#contain").append("<div class='row" + len + "'></div>");
        for (var j = 0; j < side; j++) {
            $("#contain div." + rowC + ":eq(" + i + ")").append("<div class='cell" + len + "'></div>")
        }
    }
    $("#contain").append("<div id=\"youbiao" + len + "\">");


</script>
<!--<script src="AStar.js"></script>-->
<script>



    //已确定顶点集
    var S = new Map();
    //相邻节点集
    var T = new Map();

    //源点
    var startP = createPoint();
    //当前点
    var curP = createPoint();
    //目标点
    var endP = createPoint();


    $(function () {
        init();
    });

    var findFlag = true;

    function main() {

        if (!runFlag) return;

        curP = startP;
        curP.parentX = startP.x;
        curP.parentY = startP.y;
        curP.disStart = 0;
        curP.disEnd = getDis(curP, endP);
        curP.disSum = curP.disEnd;

        S.put(curP.x + "," + curP.y, curP);


        if (debug) {
        }
        else {
            while (findFlag) {
                recentPoint();
            }

            mask();
        }


    }

    //消隐遮罩
    var maskFlag = true;

    function mask() {
        while (maskFlag) {
            maskUp(curP);
            curP = S.get(curP.parentX + "," + curP.parentY);
            if (isSamePoint(curP, startP)) maskFlag = false;
        }
    }

    function maskUp(temp) {
        if (isSamePoint(temp, endP)) {
            getObj(temp.x, temp.y).removeClass("recent");
            getObj(temp.x, temp.y).addClass("endP");
        }
        else {
            getObj(temp.x, temp.y).removeClass("recent");
            getObj(temp.x, temp.y).addClass("route");
        }

    }

    //更新距离
    function updateDis(key, temp) {
        var val = T.get(key);
        if (val == null) {
            apdMsg(temp);
            T.put(temp.x + "," + temp.y, temp);
            return;
        }
        else if (val.disSum < temp.disSum) {
            return;
        }
        else {
            apdMsg(temp);
            T.put(temp.x + "," + temp.y, temp);
        }
    }

    //单次查询
    function recentPoint() {
        var x = curP.x;
        var y = curP.y;
        var a;
        var b;
        for (var i = x - 1; i <= x + 1; i++) {
            for (var j = y - 1; j <= y + 1; j++) {
                a = i;
                b = j;
                if (a < 0) a = 0;
                if (b < 0) b = 0;
                if (a >= side) a = side - 1;
                if (b >= side) b = side - 1;
                if (a == x && b == y) {
                    continue;
                }

                //判断是否在以求节点集中
                if (S.get(a + "," + b) != null) {
                    continue;
                }

                //判断是不是墙
                if (!isWall(a, b)) {
                    var temp = createPoint(a, b);
                    temp.parentX = curP.x;
                    temp.parentY = curP.y;
                    temp.disStart = getDis(curP, temp) + curP.disStart;
                    temp.disEnd = getDis(endP, temp);
                    temp.disSum = temp.disStart + temp.disEnd;
                    updateDis(a + "," + b, temp);
                }
            }
        }
        getRectP();

    }


    //找出距离最小点
    function getRectP() {
        var tempK;
        var tempV;
        var c = true;

        if (T.isEmpty()) {
            findFlag = false;
            alert('死路')
        }
        T.each(function (key, val) {

            //以遍历集合中没有
            if (S.get(key) == null) {
                if (c) {
                    tempK = key;
                    tempV = val;
                    c=!c;
                }
                else {
                    //此处不能加等号
                    //无等号则为集合中该值第一个，有等号则为最后一个
                    //有等号则平添多步无意义值赋值操作
                    if (val.disSum < tempV.disSum) {
                        tempK = key;
                        tempV = val;
                    }
                }
            }

        });
        getObj(tempV.x, tempV.y).addClass("recent")
        T.remove(tempK);
        S.put(tempK, tempV);
        curP = tempV;
        if (isSamePoint(curP, endP)) {
            findFlag = false;
        }

    }

    //点对象
    function createPoint() {
        return {
            "x": -1,
            "y": -1,
            "parentX": -1,
            "parentY": -1,
            "disStart": -1,
            "disEnd": -1,
            "disSum": -1
        };
    }

    function createPoint(x, y) {
        return {
            "x": x,
            "y": y,
            "parentX": -1,
            "parentY": -1,
            "disStart": -1,
            "disEnd": -1,
            "disSum": -1
        };
    }

    function isSamePoint(a, b) {
        return a.x == b.x && a.y == b.y;
    }


    //根据行列获取当前div.cell
    function getObj(row, col) {
        return $("#contain div." + rowC + ":eq(" + row + ") div." + cellC + ":eq(" + col + ")")
    }

    //显示调试信息
    function apdMsg(a) {
        if (side > 10) return;
        getObj(a.x, a.y).html("");
        getObj(a.x, a.y).append("" +
            "<span>" + a.disSum + "</span>" +
            "<span>" + a.disStart + "</span>" +
            "<span>" + a.disEnd + "</span>");
    }

    //是否是墙if it's a wall return true
    function isWall(row, col) {
        return getObj(row, col).hasClass("wall");
    }

    //终点设置
    var endPFlag = false;
    var runFlag = true;
    $("div." + cellC).click(function () {
        if (!$(this).hasClass("wall")) {
            if (!endPFlag) {
                $(this).addClass("endP");
                endPFlag = true;
                endP.x = $(this).data("x");
                endP.y = $(this).data("y");
            }
            else {
                main();
                runFlag = false;
                if (debug) {
                    recentPoint();
                    // mask();
                }


            }
        }
    });

    //返回两点距离,非直线
    function getDis(a, b) {

        //非等边直角三角形求斜边长度
        // Math.floor(Math.sqrt(Math.pow(_x * 10, 2) + Math.pow(_y * 10, 2)))

        var _x = Math.abs(a.x - b.x);
        var _y = Math.abs(a.y - b.y);
        if (_x == 0 && _y == 0) return 0;
        if (_x == 0)
            return _y * 10;
        if (_y == 0)
            return _x * 10;
        if (_x == _y) {
            return _x * 14;
        }
        if (_x > _y) {
            var c = 0;
            while (_x != _y) {
                c++;
                _x--;
            }
            return c * 10 + _x * 14;
        }
        if (_x < _y) {
            var c = 0;
            while (_x != _y) {
                c++;
                _y--;
            }
            return c * 10 + _x * 14;
        }

    }


    //初始化
    function init() {
        if (test == 0) {
            //初始化墙
            var count = Math.random() * side + side * side / 5;
            for (var i = 0; i < count; i++) {
                var row = Math.floor(Math.random() * side);
                var col = Math.floor(Math.random() * side);
                getObj(row, col).addClass("wall");
            }

            //初始化坐标
            for (var i = 0; i < side; i++) {
                for (var j = 0; j < side; j++) {
                    getObj(i, j).attr("data-x", i);
                    getObj(i, j).attr("data-y", j);
                }
            }

            //出生点
            var row = Math.floor(Math.random() * side);
            var col = Math.floor(Math.random() * side);
            if (isWall(row, col)) {
                getObj(row, col).removeClass("wall");
            }
            $("#youbiao" + len).css("left", "calc(" + len + "px*" + col + ")");
            $("#youbiao" + len).css("top", "calc(" + len + "px*" + row + ")");
            startP.x = row;
            startP.y = col;
        }

        else if (test == 1 || test == 2) {
            if (test == 1) {
                //初始化墙
                for (var i = 2 + (side - 10) / 2; i < 8 + (side - 10) / 2; i++) {
                    if (i == 2 + (side - 10) / 2) {
                        for (var j = 2 + (side - 10) / 2; j < 8 + (side - 10) / 2; j++) {
                            getObj(i, j).addClass("wall");
                        }
                    }
                    else {
                        getObj(i, 2 + (side - 10) / 2).addClass("wall");
                        getObj(i, 7 + (side - 10) / 2).addClass("wall");
                    }

                }
            }
            else if (test == 2) {
                //初始化墙
                for (var j = 0; j < side; j++) {
                    getObj(side / 2, j).addClass("wall");
                }
                //初始化墙
                for (var i = side - 4; i <= side - 1; i++) {
                    if (i == side - 4 || i==side-1) {
                        for (var j = 3; j < 7; j++) {
                            getObj(i, j).addClass("wall");
                        }
                    }
                    else {
                        getObj(i,3).addClass("wall");
                        getObj(i, 6).addClass("wall");
                    }

                }
            }


            //初始化坐标
            for (var i = 0; i < side; i++) {
                for (var j = 0; j < side; j++) {
                    getObj(i, j).attr("data-x", i);
                    getObj(i, j).attr("data-y", j);
                }
            }

            //出生点
            //             var row=Math.floor(Math.random()*3.5+5);
            //             var col=Math.floor(Math.random()*1.5+4);
            var row = 8 + (side - 10) / 2;
            var col = 5 + (side - 10) / 2;
            if (isWall(row, col)) {
                getObj(row, col).removeClass("wall");
            }
            $("#youbiao" + len).css("left", "calc(" + len + "px*" + col + ")");
            $("#youbiao" + len).css("top", "calc(" + len + "px*" + row + ")");
            startP.x = row;
            startP.y = col;
        }

    }



</script>
</html>
